In general, strong market demand for computing systems with faster processing speeds has been met by technical innovations in multicore, multithreaded processor chips and the development of parallel programming methodologies to support concurrent access to shared resources. In particular, transactional memory makes it easier to write parallel programs and allow different threads to be processed simultaneously thereby gaining extremely high processing efficiencies. Transactional memory programming techniques allow transactions that do not overlap in data accesses to run uninterrupted in parallel. For purposes of data consistency in transactional programming, certain sections of the program have to execute atomically, whereby transactional memory systems and methods allow programs to read and modify memory locations as a single atomic operation. Such sections specified by the programmer as atomic are often called atomic sections, atomic transactions, or transactions for short.
In particular, a transaction is a finite sequence of steps (program instructions) executed by a single thread, including memory reads and writes access operations. A transaction may execute serially such that the steps of one transaction do not interleave with the steps of another. TM systems provide a mechanism for guaranteeing the atomicity of atomic sections by guaranteeing that these memory accesses appear to an external observer take effect all at once, i.e., in one atomic step, where a transaction either commits or aborts.
One of the main functions of TM systems is the detection of conflicts among concurrent transactions. Conflict detection is the process of identifying when two or more transactions conflict. Multiple transactions can be executed concurrently if they are not in conflict. Two transactions are said to be in conflict if they access the same memory location and at least one of the accesses is a write. Conflicts can exist when a transaction writes to memory that another transaction then reads or writes (write after write, write after read), or when a transaction reads memory that is then used in another transaction's write (read after write). Unlimited readers, on the other hand, can read the same piece of memory without any conflict (read after read).
A problem that designers of TM systems face is the choice of the unit of conflict detection (whether based on fixed-size blocks of memory or data objects). TM systems use a memory granularity size of either word (block) or object for transactions. Word (block) memory granularity allows transactions to read and write at the machine's architectural word size. Object memory granularity allows transactions to read and write at the object level. For example. FIG. 1 schematically illustrates transactional memory (10) for a conventional TM system that implements conflict detection at memory block granularity. FIG. 2 schematically illustrates a transactional memory (20) for a conventional TIM system that implements conflict detection as object granularity.
In FIG. 1, the transactional memory (10) comprises a plurality of contiguous memory locations [L0, L1 . . . L9i-1), L(i)] in which the memory locations are divided into blocks [MB0, MB1, . . . MB(n)] of memory comprising 3 contiguous memory locations that are accessed by transactions as a memory access unit and where the conflict detection granularity is at the block level. In FIG. 2, the transactional memory (20) comprises a plurality of contiguous memory locations [L0, L1 . . . L(i-1), L(i)] in which the memory locations include objects [O0, O1, . . . O(m)], each containing one or more contiguous memory locations that are accessed by transactions as a memory access unit. An object corresponds to a data unit as usually defined in an object-oriented programming language and occupies some number of memory locations.
In conventional TM systems such as depicted in FIGS. 1 and 2, conflict detection unit granularity is typically the same as the memory access unit (e.g., memory word or object). In general, object granularity conflict detection will identify a conflict between two transactions that access the same object if at least one transaction writes a field of the object, even if the two transactions access disjoint fields of the object. In this regard, object granularity conflict detection may therefore limit concurrency on large objects. For example, in a conventional TM system, a conflict is deemed to exist when a transaction writes to an element of an object and one or more other transactions access disjoint elements of the object. On the other hand, depending on the block size, conflict detection at a word (block)-based granularity may allow for conflict detection at finer grain concurrency by allowing concurrent access to different fields of the same object, but will have higher overhead due to a conflict detection evaluation that must be performed at each memory access.
If the unit of conflict detection is large, it is likely that two transactions that do not have inherent conflicts are mistakenly considered by the TM system to be in conflict simply because they access different parts of the same conflict unit. While this does not violate the safety guarantees of TM systems, it reduces performance by reducing concurrency unnecessarily, as in such a case at least one of these transactions need to be delayed or restarted. On the other hand, if the unit of conflict detection is small, this increases the record keeping overheads in time as well as space. These overheads are unnecessary if adjacent locations are always accessed together in the same transaction. Furthermore, if non-adjacent locations are accessed together in the same transactions but rarely in different transactions, where it would be beneficial to have these locations in the same conflict unit, existing TM systems are unable to exploit this possibility.